﻿#pragma once
#include<iostream>
#include<vector>
using namespace std;
	// 请完成哈希表的如下操作
// 哈希函数采用除留余数法﻿
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	// 哈希表中支持字符串的操作
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash *= 31;
				hash += e;
			}

			return hash;
		}
	};
	//template<class T>
	//struct K_KeyOfT
	//{
	//	int operator()(const T& key)
	//	{
	//		return key;
	//	}
	//};
	//template<class K,class V>
	//struct P_KeyOfT
	//{
	//	pair<K, V> operator()(const pair<K, V>& kv)
	//	{
	//		return kv.first;
	//	}
	//};

	// 以下采用开放定址法，即线性探测解决冲突
	namespace open_address
	{
		enum State
		{
			EXIST,
			EMPTY,
			DELETE
		};

		template<class K, class V>
		struct HashData
		{
			pair<K, V> _kv;
			State _state = EMPTY;
		};

		template<class K, class V, class Hash = HashFunc<K>>
		class HashTable
		{
		public:
			HashTable()
			{
				_tables.resize(10);
			}
			bool Insert(const pair<K, V>& kv)
			{
				//Hash has;
				//size_t hashi = has(kv.first) % _tables.size();

				if (_n * 10 / _tables.size() >= 7)
				{
					//HashT* newtab = new HashT(_tables.size() * 2);
				//	vector<HashData<K, V>> newtab(_tables.size() * 2);
				//	for (size_t i = 0; i < _tables.size(); i++)
				//	{
				//		while (_tables[i]._state == EMPTY)
				//		{
				//			++i;
				//			i %= _tables.size();
				//		}
				//		size_t hashii = has(_tables[i]._kv.first) % newtab.size();
				//		while (1)
				//		{
				//			if (newtab[hashii]._state == EXIST)++hashii;
				//			else
				//			{
				//				newtab[hashii]._kv = _tables[i]._kv;
				//				newtab[hashii]._state = EXIST;
				//				break;
				//			}
				//			hashii %= newtab.size();
				//		}
				//	}
				//	_tables.swap(newtab);
				//}
				//for (size_t i = hashi; i < _tables.size();)
				//{	
				//	if (_tables[i]._kv.first == kv.first)return false;
				//	if (_tables[i]._state == EXIST)++i;
				//	else
				//	{
				//		_tables[i]._state = EXIST;
				//		_tables[i]._kv = kv;
				//		break;
				//	}
				//	i %= _tables.size();
				//}
				//++_n;
				//return true;//我写的
					HashTable<K, V, Hash> newHT;
					newHT._tables.resize(_tables.size() * 2);
					for (size_t i = 0; i < _tables.size(); i++)
					{
						if (_tables[i]._state == EXIST)
						{
							newHT.Insert(_tables[i]._kv);
						}
					}

					_tables.swap(newHT._tables);
				}
				Hash hs;
				size_t hashi = hs(kv.first) % _tables.size();
				while (_tables[hashi]._state == EXIST)
				{
					++hashi;
					hashi %= _tables.size();
				}
				_tables[hashi]._kv = kv;
				_tables[hashi]._state = EXIST;
				++_n;

				return true;
			}
			HashData<K, V>* Find(const K& key)
			{
				//Hash has;
				//size_t hashi = has(key) % _tables.size();
				//for (size_t i = hashi; i < _tables.size();)
				//{
				//	if (_tables[i]._state == EXIST && _tables[i]._kv.first == key)return &_tables[i];
				//	else
				//	{
				//		if (_tables[i]._state != EMPTY)++i;
				//		else
				//		{
				//			return nullptr;
				//		}
				//		i %= _tables.size();
				//	}
				//}//我写的
				Hash hs;
				size_t hashi = hs(key) % _tables.size();
				while (_tables[hashi]._state != EMPTY)
				{
					if (_tables[hashi]._state == EXIST
						&& _tables[hashi]._kv.first == key)
					{
						return &_tables[hashi];
					}

					++hashi;
					hashi %= _tables.size();
				}
				return nullptr;
			}
			bool Erase(const K& key)
			{
				HashData<K, V>* tamp = Find(key);
				if (tamp)
				{
					tamp->_state = DELETE;
					return true;
				}
				else
					return false;
			}
		private:
			vector<HashData<K, V>> _tables;
			size_t _n = 0;  // 表中存储数据个数
		};
	}
	// 实现完成后，请对整形 和 字符串完成测试
	namespace hash_bucket
	{

		template<class T>
		struct HashNode
		{
			T _data;
			HashNode<T>* _next;
			HashNode(const T& data)
				:_data(data)
				, _next(nullptr)
			{
			}
		};
		// K 为 T 中key的类型
		// T 可能是键值对，也可能是K
		// KeyOfT: 从T中提取key
		// Hash将key转化为整形，因为哈市函数使用除留余数法

		template<class K, class T, class Hash>
		class HashTable
		{

			typedef HashNode<T> Node;
		public:
			HashTable()
			{
				_tables.resize(10, nullptr);
			}

			// 哈希桶的销毁
			~HashTable()
			{
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];

					while (cur)
					{
						Node* next = cur->_next;
						delete cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_n = 0;
			}

			// 插入值为data的元素，如果data存在则不插入
			bool Insert(const T& data)
			{
				//Hash hot;
				//size_t hashi = hot(data) % _tables.size();
				//Node* cur = _tables[hashi];
				//while (cur) 
				//{
				//	if (cur->_data == data) return false; // 发现重复
				//	cur = cur->_next;
				//}
				//if (_n == _tables.size())
				//{
				//	//HashTable<K,T,Hash> newTable(_tables.size() * 2);
				//	vector<Node*> newTable(_tables.size() * 2);
				//	for (size_t i = 0; i < _tables.size(); i++)
				//	{
				//		while (_tables[i])
				//		{
				//			Node* next = _tables[i]->_next;
				//			size_t newHash = hot(_tables[i]->_data) % newTable.size();
				//			//if(newTable[newHash])//错误的
				//			_tables[i]->_next = newTable[newHash];
				//			newTable[newHash] = _tables[i];
				//			_tables[i] = next;
				//		}
				//	}
				//	_tables.swap(newTable);
				//	hashi = hot(data) % _tables.size();
				//}
				//if (_tables[hashi] == nullptr)
				//{
				//	_tables[hashi] = new Node(data);
				//}
				//else
				//{
				//	Node* newnode = new Node(data);
				//	newnode->_next = _tables[hashi];
				//	_tables[hashi] = newnode;
				//}
				//++_n;
				//return true;
				//我写的
				Hash hs;
				if (_n == _tables.size())
				{
					vector<Node*> newtables(_tables.size() * 2, nullptr);
					for (size_t i = 0; i < _tables.size(); i++)
					{
						Node* cur = _tables[i];
						while (cur)
						{
							Node* next = cur->_next;
							// 旧表中节点，挪动新表重新映射的位置
							size_t hashi = hs(cur->_data) % newtables.size();
							// 头插到新表
							cur->_next = newtables[hashi];
							newtables[hashi] = cur;
							cur = next;
						}
						_tables[i] = nullptr;
					}
					_tables.swap(newtables);
				}
				// 头插
				size_t hashi = hs(data) % _tables.size();
				Node* newnode = new Node(data);
				newnode->_next = _tables[hashi];
				_tables[hashi] = newnode;
				++_n;
				return true;
			}

			// 在哈希桶中查找值为key的元素，存在返回true否则返回false﻿
			Node* Find(const K& key)
			{
				Hash hot;
				size_t hashi = hot(key) % _tables.size();
				Node* cur = _tables[hashi];
					while (cur)
					{
						if(cur->_data == key)
							return cur;
						cur = cur->_next;
					}
					return nullptr;

					//Hash hs;
					//size_t hashi = hs(key) % _tables.size();
					//Node* cur = _tables[hashi];
					//while (cur)
					//{
					//	if (cur->_kv.first == key)
					//	{
					//		return cur;
					//	}
					//	cur = cur->_next;
			}
			// 哈希桶中删除key的元素，删除成功返回true，否则返回false
			bool Erase(const K& key)
			{
				Hash hot;
					size_t hashi = hot(key) % _tables.size();
					Node* cur = _tables[hashi];
					Node* prev = nullptr;
					while (cur)
					{
						if (cur->_data == key)
						{
							if (cur == _tables[hashi])
							{
								_tables[hashi]->_next = cur->_next;
							}
							else
							{
								prev->_next = cur->_next;
							}
							delete cur;
							--_n;
							return true;
						}
						prev = cur;
						cur = cur->_next;
					}

					return false;

			//	Hash hs;
			//	size_t hashi = hs(key) % _tables.size();
			//	Node* prev = nullptr;
			//	Node* cur = _tables[hashi];
			//	while (cur)
			//	{
			//		if (cur->_kv.first == key)
			//		{
			//			if (prev == nullptr)
			//			{
			//				_tables[hashi] = cur->_next;
			//			}
			//			else
			//			{
			//				prev->_next = cur->_next;
			//			}
			//			delete cur;
			//			--_n;
			//			return true;
			//		}
			//		prev = cur;
			//		cur = cur->_next;
			//	}
			//	return false;
			}

		private:
			vector<Node*> _tables;  // 指针数组
			size_t _n = 0;			// 表中存储数据个数
		};
	}